package ca.swank.hq.ai;

import ca.swank.hardquor.*;

import java.util.LinkedList;
import java.util.TreeSet;
import java.util.Comparator;
import java.util.ArrayList;
import java.util.Iterator;
// trove collections are fast but require trove knowledge
import gnu.trove.TLinkedList;


/**
 * an optimized SmartBoard which caches generated information so that it does
 * not need to be generated multiple times. This implementation caches move information
 * on a stack that can grow unbounded. To release this memory, call the clearCache()
 * method.
 */
public class CachingSmartBoard extends SmartBoard
{
  @Override
	public Object clone() {
		return new CachingSmartBoard(this);
	}

private int[][][] distanceBoardCache;
  private LinkedList[] dbcStack;

  private static final int[][] NULL_DISTANCE_BOARD = new int[][] { };

  public CachingSmartBoard()
  { super();
    clearCache();
  }

  public CachingSmartBoard(CachingSmartBoard other)
  { super(other);
    clearCache();
  }

  public CachingSmartBoard(int width, int height, int playerStartWalls)
  { super(width, height, playerStartWalls);
    clearCache();
  }

  /**
   * clears the distance board cache, freeing memory of cached boards that
   * will not be useful in future computations. It is appropriate to clear the
   * cache whenever an AI player commits to a move; in effect when a move
   * is made that will not be un-made.
   */
  public void clearCache()
  { distanceBoardCache = new int[2][][];
    dbcStack = new LinkedList[2];
    dbcStack[0] = new LinkedList();
    dbcStack[1] = new LinkedList();
    distanceBoardCache[0] = super.getDistanceHomeBoard(0);
    distanceBoardCache[1] = super.getDistanceHomeBoard(1);
  }

  private void pushDistanceBoardCache(int[] a1, int[] a2, int[] b1, int[] b2)
  { // push the distance boards
    for(int i = 0; i < 2; i++)
    { dbcStack[i].addFirst(distanceBoardCache[i]);
      rebuildDistanceHomeBoard(i, a1, a2, b1, b2);
    }
  }

  private void popDistanceBoardCache()
  { // pop the distance boards
    for(int i = 0; i < 2; i++)
    { distanceBoardCache[i] = (int[][])dbcStack[i].removeFirst();
    }
  }

  public void makeMove(int[] a1, int[] a2, int[] b1, int[] b2)
  { super.makeMove(a1, a2, b1, b2);
    pushDistanceBoardCache(a1, a2, b1, b2);
  }

  public void unMove(int[] a1, int[] a2, int[] b1, int[] b2)
  { super.unMove(a1, a2, b1, b2);
    popDistanceBoardCache();
  }

  public int[][] getDistanceHomeBoard(int player)
  { return distanceBoardCache[player];
  }

  /**
   * builds a distance board without rebuilding the entire thing. rather, it takes
   * the distance board before the move, and modifies it.
   */
  private void rebuildDistanceHomeBoard(int player, int[] a1, int[] a2, int[] b1, int[] b2)
  {
    // use the cached distance board one move back to build a new distance board
    int[][] original = (int[][])dbcStack[player].getFirst();

    //# create an array the size of the board
    distanceBoardCache[player] = new int[original.length][original[0].length];

    //# set origin cells in array to 0
    //# add origin cells to queue
    TLinkedList bfstQueue = new TLinkedList();

    int threshHold = Integer.MAX_VALUE;
    if(original[a1[0]][a1[1]] < threshHold) threshHold = original[a1[0]][a1[1]];
    if(original[a2[0]][a2[1]] < threshHold) threshHold = original[a2[0]][a2[1]];
    if(original[b1[0]][b1[1]] < threshHold) threshHold = original[b1[0]][b1[1]];
    if(original[b2[0]][b2[1]] < threshHold) threshHold = original[b2[0]][b2[1]];

    for(int y = distanceBoardCache[player][0].length - 1; y >= 0; y--)
    { for(int x = 0; x < distanceBoardCache[player].length; x++)
      { if(original[x][y] > threshHold)
        { distanceBoardCache[player][x][y] = Integer.MAX_VALUE;
        } else if(original[x][y] == threshHold)
        { distanceBoardCache[player][x][y] = original[x][y];
          bfstQueue.addLast(coords[x][y]);
        } else
        { distanceBoardCache[player][x][y] = original[x][y];
        }
      }
    }

    //# while cells in queue, add neighbours to queue, set neighbours value plus 1
    breadthFirstDistanceMap(bfstQueue, distanceBoardCache[player]);
  }
}